import java.util.*;

class ListNode {
  int val;
  ListNode next = null;
  public ListNode(int val) {
    this.val = val;
  }
}
public class demo {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */

    // 1.使用栈
    public ListNode ReverseList (ListNode head) {
        // write code here
        Stack<ListNode> stack = new Stack<>();

        // 将链表node存到 栈中
        while (head != null) {
            stack.push(head);
            head = head.next;
        }

        // 栈如果为空就 返回null
        if (stack.isEmpty()) {
            return null;
        }

        // 先从栈中取出一个
        ListNode node = stack.pop();
        ListNode dummy = node;

        // 在判断栈中是否为空 不为空就出栈
        while (!stack.isEmpty()) {
            node.next = stack.pop();
            node = node.next;
        }
        node.next = null;
        return dummy;
    }





    // 2.双链表
    public ListNode ReverseList2 (ListNode head) {
        // 新链表 头节点
        ListNode newHead = null;
        // 中间节点
        ListNode temp;

        while (head != null) {
            // 保存 head 的下一个节点
            temp = head.next;
            // 将head指向的指向空 或者是 指向前一个节点(原head节点)
            head.next = newHead;
            // 更新节点
            newHead = head;
            head = temp;
        }

        return newHead;
    }

}

